package graph;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import constraint.Constraint;

import edu.uci.ics.jung.graph.Graph;
import grammar.Design;

public final class GraphMatcher {
    
    /**
     * Searches hierarchically for graph matches.
     * 
     * @param designToFind
     * @param designToSearch
     * @return
     */
    public static List<GraphMatch> findGraphMatches(Design designToFind, Design designToSearch) {
        List<GraphMatch> matchesProduct = new ArrayList<GraphMatch>();
        if (designToFind.hasProduct()==false || designToSearch.hasProduct()==false) {
            return matchesProduct;
        }
        GraphMatch productMatch = new GraphMatch(designToFind, designToSearch);
        productMatch.addMatch(designToFind.getProduct(), designToSearch.getProduct());
        matchesProduct.add(productMatch);
        
        List<SubGGraph> assemblyChildToFind = designToFind.getChildSubgraphs(NodeType.ASSEMBLY);
        List<SubGGraph> assemblyChildToSearch = designToSearch.getChildSubgraphs(NodeType.ASSEMBLY);
        List <GraphMatch>comboMatches = new ArrayList<GraphMatch>();
        
        if (assemblyChildToSearch.isEmpty()) {
            return matchesProduct;
        }
        
        for (GraphMatch matchProduct : matchesProduct) {
            for (SubGGraph toFindGraph : assemblyChildToFind) {
                GNode toSearchParent = matchProduct.getToFindMatch(toFindGraph.parent);
                for (SubGGraph toSearchGraph : assemblyChildToSearch) {
                    if (toSearchParent == toSearchGraph.parent) {
                        List<GraphMatch> matchesPart = findGraphMatchesAtLevel(designToFind, designToSearch, toFindGraph.getGraphOfType(NodeType.ASSEMBLY), 
                                toSearchGraph.getGraphOfType(NodeType.ASSEMBLY)); 
                        comboMatches.addAll(combineMatches(matchProduct, matchesPart));
                    }
                }
            }
        }

        List<SubGGraph> partChildToFind = designToFind.getChildSubgraphs(NodeType.PART);
        List<SubGGraph> partChildToSearch = designToSearch.getChildSubgraphs(NodeType.PART);
        List <GraphMatch>combo2Matches = new ArrayList<GraphMatch>();      
        
        if (partChildToSearch.isEmpty()) {
            return comboMatches;
        }
        
        for (GraphMatch comboMatch : comboMatches) {
            for (SubGGraph toFindGraph : partChildToFind) {
                GNode toSearchParent = comboMatch.getToFindMatch(toFindGraph.parent);
                for (SubGGraph toSearchGraph : partChildToSearch) {
                    if (toSearchParent == toSearchGraph.parent) {
                        List<GraphMatch> matchesPart = findGraphMatchesAtLevel(
                                designToFind, designToSearch,
                                toFindGraph.getGraphOfType(NodeType.PART), 
                                toSearchGraph.getGraphOfType(NodeType.PART)); 
                        combo2Matches.addAll(combineMatches(comboMatch, matchesPart));
                    }
                }
            }
        }

        /**
         * This is a hack!! Why are their incomplete matches here????
         */
        List <GraphMatch>combo3Matches = new ArrayList<GraphMatch>();
        int matchSize = 0;
        for (GraphMatch match : combo2Matches) {
            if (match.size() > matchSize) {
                combo3Matches.clear();
                combo3Matches.add(match);
                matchSize=match.size();
            } else if (match.size() == matchSize) {
                combo3Matches.add(match);
            }
        }
        return combo3Matches;
    }
    
    private static List<GraphMatch> combineMatches(GraphMatch match, List<GraphMatch> matches) {
        List <GraphMatch>comboMatches = new ArrayList<GraphMatch>();
        for (GraphMatch match2 : matches) {
            comboMatches.add(match.addMatch(match2));
        }
        return comboMatches;
    }

    private static List<GraphMatch> findGraphMatchesAtLevel(Design toFind, Design toSearch,
            Graph<GNode, Constraint> graphToFind, 
            Graph<GNode, Constraint> graphToSearch) {
        List<GraphMatch> proposedMatches = buildInitialCandidateMatches(toFind, toSearch, graphToFind, graphToSearch); 
        
        List<GraphMatch> completeMatches = new ArrayList<GraphMatch>();
        List<GraphMatch> incompleteMatches = new ArrayList<GraphMatch>();
        while (proposedMatches.size() > 0) {
            GraphMatch match = proposedMatches.get(0);
            proposedMatches.addAll(buildMatch(match, graphToFind, graphToSearch));
            if (match.isComplete(graphToFind.getVertexCount())) {
                if(!isMatchStored(match, completeMatches)) {
                    completeMatches.add(match);
                }
            } else {
                incompleteMatches.add(match);
            }
            proposedMatches.remove(0);
        }
        return completeMatches;
    }

    private static boolean isMatchStored(GraphMatch match,
            List<GraphMatch> matches) {
        for (GraphMatch m : matches) {
            if(m.isSame(match)) {
                return true;
            }
        }
        return false;
    }

    private static List<GraphMatch> buildMatch(
            GraphMatch match,
            Graph<GNode, Constraint> graphToFind,
            Graph<GNode, Constraint> graphToSearch) {
        
        List<GNode> unmatchedNeighbors = match.getUnmatchedToFindNeighbors();
        List<GraphMatch> proposedMatches = new ArrayList<GraphMatch>();
        boolean foundAMatch = true;
        while (unmatchedNeighbors.size() > 0 && foundAMatch ) {
            foundAMatch = false;
            for (GNode unmatchedNeighbor : unmatchedNeighbors) {
                List<GNode> matchedNodes = findMatchingNodes(unmatchedNeighbor, match, graphToFind, graphToSearch);
                //add the first one to this match and the rest to a new proposed match
                if (matchedNodes.size() > 0) {
                    foundAMatch = true;
                    for (int i = 1; i < matchedNodes.size(); i++) {
                        GraphMatch copy = match.copy();
                        copy.addMatch(unmatchedNeighbor, matchedNodes.get(i));
                        proposedMatches.add(copy);
                    }
                    match.addMatch(unmatchedNeighbor, matchedNodes.get(0));
                }
            }
            unmatchedNeighbors = match.getUnmatchedToFindNeighbors();
        }
        return proposedMatches;
    }

    
    /**
     * Find matches for nodeToFind in the graphToSearch
     * 
     * @param nodeToFind the node in graphToFind that we are looking for matches for
     * @param match 
     * @param graphToFind
     * @param graphToSearch
     * @return
     */
    private static List<GNode> findMatchingNodes(
            GNode nodeToFind, 
            GraphMatch match,
            Graph<GNode, Constraint> graphToFind,
            Graph<GNode, Constraint> graphToSearch) {        
        List<GNode> matchedNeighbors = match.findMatchedToFindNeighbors(nodeToFind);
        
        Set<GNode> cand1 = new HashSet<GNode>();
        
        boolean firstTime = true;
        for (GNode matchedNeighbor : matchedNeighbors) {
            
            GNode matchedNode = match.getToFindMatch(matchedNeighbor);
            
            List<GNode> unmatchedToSearchNeighbors = new ArrayList<GNode>(graphToSearch.getNeighbors(matchedNode));
            unmatchedToSearchNeighbors.removeAll(match.matchedNodes());
            if (firstTime) {
                cand1.addAll(unmatchedToSearchNeighbors);
                firstTime = false;
            } else {
                cand1.retainAll(unmatchedToSearchNeighbors);
            }
        }
        List<GNode> cand2 = findCandidatesWithMatchingLabels(nodeToFind, new ArrayList<GNode>(cand1));
        List<GNode> cand3 = findCandidatesWithMinimumDegree(graphToFind.degree(nodeToFind), cand2, graphToSearch);
        return cand3;
    }

    private static List<GraphMatch> buildInitialCandidateMatches(Design toFind, Design toSearch,
            Graph<GNode, Constraint> graphToFind, Graph<GNode, Constraint> graphToSearch) {

        List<GraphMatch> initialMatches = new ArrayList<GraphMatch>();
        List<GNode> startingPointsToFind = highestDegreeNodes(graphToFind);
        for(GNode startingPointToFind : startingPointsToFind) {
            GraphMatch graphMatch = new GraphMatch(toFind, toSearch);
            List<GNode> candidateMatches = findCandidates(startingPointToFind, graphToFind, graphToSearch, graphMatch);
            for (GNode candidate : candidateMatches) {
                graphMatch = new GraphMatch(toFind, toSearch);
                graphMatch.addMatch(startingPointToFind, candidate);
                initialMatches.add(graphMatch);                
            }
        }
        return initialMatches;
    }

    private static List<GNode> findCandidates(GNode node, 
            Graph<GNode, Constraint> graphToFind,
            Graph<GNode, Constraint> graphToSearch, 
            GraphMatch graphMatch) {
        // a node in the graphToSearch is a candidate if it is not in the match, it has the labels that the node has, 
        // it's degree is at greater than or equal to the node
        List<GNode> cand1 = availableNodesToSearch(node, graphMatch, graphToSearch);
        List<GNode> cand2 = findCandidatesWithMatchingLabels(node, cand1);
        List<GNode> cand3 = findCandidatesWithMinimumDegree(graphToFind.degree(node), cand2, graphToSearch);
        return cand3;
    }

    private static List<GNode> availableNodesToSearch(GNode node, GraphMatch graphMatch, Graph<GNode, Constraint> graphToSearch) {
        List<GNode> cand = new ArrayList<GNode>(graphToSearch.getVertices());
        cand.removeAll(graphMatch.matchedNodes());
        return cand;
    }

    private static List<GNode> findCandidatesWithMinimumDegree(int degree, List<GNode> candidates, 
            Graph<GNode, Constraint> graphToSearch) {
        List<GNode> highEnoughDegree = new ArrayList<GNode>();
        for (GNode candidate: candidates) {
            if (graphToSearch.degree(candidate) >= degree) {
                highEnoughDegree.add(candidate);
            }
        }
        return highEnoughDegree;
    }

    private static List<GNode> findCandidatesWithMatchingLabels(
            GNode node, List<GNode> candidates) {
        List<GNode> sameLabels = new ArrayList<GNode>();
        for (GNode candidate: candidates) {
            if (node.hasSubsetOfLabels(candidate)) {
                sameLabels.add(candidate);
            }
        }
        return sameLabels;
    }

    private static List<GNode> highestDegreeNodes(Graph<GNode, Constraint> graph) {
        int largestDegree = 0;
        List<GNode> nodes = new ArrayList<GNode>();
        for(GNode node : graph.getVertices()) {
            int degree = graph.degree(node);
            if (degree > largestDegree) {
                largestDegree = degree;
                nodes.clear();
                nodes.add(node);
            } else if (degree == largestDegree) {
                nodes.add(node);
            }
        }
        return nodes;
    }
}
